package com.bo.day20231212;

import java.util.HashMap;

/**
 * 前缀数版本1
 *
 * @Author: gpb
 * @Date: 2023/12/12 9:33
 * @Description:
 */
public class TrieTreeVersion1 {



    public static void main (String[] args) {
        int arrLen = 100;
        int strLen = 20;
        int testTimes = 100000;
        for (int i = 0; i < testTimes; i++) {
            String[] arr = generateRandomStringArray(arrLen, strLen);
            TrieVersion1 trie1 = new TrieVersion1();
            Right right = new Right();
            for (int j = 0; j < arr.length; j++) {
                double decide = Math.random();
                if (decide < 0.25) {
                    trie1.insert(arr[j]);
                    right.insert(arr[j]);
                } else if (decide < 0.5) {
                    trie1.delete(arr[j]);
                    right.delete(arr[j]);
                } else {
                    int ans1 = trie1.prefixNumber(arr[j]);
                    int ans3 = right.prefixNumber(arr[j]);
                    if (ans1 != ans3) {
                        System.out.println("ans1: " + ans1);
                        System.out.println("ans3: " + ans3);
                        System.out.println("Oops!");
                    }
                }
            }
        }
        System.out.println("finish!");

    }


    public static class Node {
        /**
         * 节点经过的数量
         */
        private int pass;

        /**
         * 以这个节点结束的数量
         */
        private int end;

        /**
         * 路线
         */
        private Node[] nexts;

        public Node () {
            this.pass = 0;
            this.end = 0;
            /**
             * 只能存储a-z的字符串
             * 使用ASCII来计算路线
             * 比如
             * 'a'-'a'=0
             * 'b'-'a'=1
             */
            this.nexts = new Node[26];
        }
    }

    /**
     * 前缀树
     */
    public static class TrieVersion1 {
        /**
         * 前缀树的根节点
         */
        private Node root;

        public TrieVersion1 () {
            this.root = new Node();
        }

        /**
         * 添加方法
         *
         * @param word
         */
        public void insert (String word) {
            if (word == null) {
                return;
            }
            char[] chars = word.toCharArray();
            Node p = root;
            p.pass++;
            for (int i = 0; i < chars.length; i++) {
                // 找路线
                int index = chars[i] - 'a';
                if (p.nexts[index] == null) {
                    p.nexts[index] = new Node();
                }
                p = p.nexts[index];
                p.pass++;
            }
            // 到了终点 end++
            p.end++;
        }

        /**
         * 删除这个单词的路线,需要防止内存泄漏
         * 删除经过的几点的次数
         *
         * @param word
         */
        public void delete (String word) {
            if (search(word) == 0) {
                // 如果这个路线不存在就结束
                return;
            }
            char[] chars = word.toCharArray();
            Node p = root;
            p.pass--;
            for (int i = 0; i < chars.length; i++) {
                // 找路线
                int index = chars[i] - 'a';
                if (--p.nexts[index].pass == 0) {
                    // 如果这个经过节点-1等于0的话
                    // 说明这条路线只有这个一个单词
                    // 可以直接断开引用
                    p.nexts[index] = null;
                    return;
                }
                p = p.nexts[index];
            }
            p.end--;
        }


        /**
         * 查询这个单词添加过几次
         * 返回这个end值即可
         *
         * @param word
         * @return
         */
        public int search (String word) {
            if (word == null) {
                return 0;
            }
            char[] chars = word.toCharArray();
            Node p = root;
            for (int i = 0; i < chars.length; i++) {
                // 找路线
                int index = chars[i] - 'a';
                if (p.nexts[index] == null) {
                    // 如果没有这条路线说明,这个单词不存在
                    // return 0;
                    return 0;
                }
                p = p.nexts[index];
            }
            return p.end;
        }

        /**
         * 所有加入的字符串中
         * 有几个是以为pre这个字符作为前缀
         * 返回这个字符结束的pass即可
         *
         * @param prefix
         * @return
         */
        public int prefixNumber (String prefix) {
            if (prefix == null) {
                return 0;
            }
            char[] chars = prefix.toCharArray();
            Node p = root;
            for (int i = 0; i < chars.length; i++) {
                // 找路线
                int index = chars[i] - 'a';
                if (p.nexts[index] == null) {
                    // 如果没有这条路线说明,这个单词不存在
                    return 0;
                }
                p = p.nexts[index];
            }
            return p.pass;
        }
    }

    public static class Right {

        private HashMap<String, Integer> box;

        public Right() {
            box = new HashMap<>();
        }

        public void insert(String word) {
            if (!box.containsKey(word)) {
                box.put(word, 1);
            } else {
                box.put(word, box.get(word) + 1);
            }
        }

        public void delete(String word) {
            if (box.containsKey(word)) {
                if (box.get(word) == 1) {
                    box.remove(word);
                } else {
                    box.put(word, box.get(word) - 1);
                }
            }
        }

        public int search(String word) {
            if (!box.containsKey(word)) {
                return 0;
            } else {
                return box.get(word);
            }
        }

        public int prefixNumber(String pre) {
            int count = 0;
            for (String cur : box.keySet()) {
                if (cur.startsWith(pre)) {
                    count += box.get(cur);
                }
            }
            return count;
        }
    }


    // for test
    public static String generateRandomString (int strLen) {
        char[] ans = new char[(int) (Math.random() * strLen) + 1];
        for (int i = 0; i < ans.length; i++) {
            int value = (int) (Math.random() * 6);
            ans[i] = (char) (97 + value);
        }
        return String.valueOf(ans);
    }

    // for test
    public static String[] generateRandomStringArray (int arrLen, int strLen) {
        String[] ans = new String[(int) (Math.random() * arrLen) + 1];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = generateRandomString(strLen);
        }
        return ans;
    }
}
